package hiho.ku._1149;

import java.util.Scanner;

public class Main {
	
	private static final int BIGINT = 100007;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for (int i = 1; i <= t; i++) {
			System.out.print("Case #" + i + ": ");
			run(in);
		}
	}
	
	private static void run(Scanner in) {
		String s = in.next();
		int n = s.length();
		int[][] f = new int[n][n];
		for (int i = 0; i < n; i++)
			f[i][i] = 1;
		for (int i = 1; i < n; i++)
			for (int j = 0; j + i < n; j++)
				f[j][j + i] = (BIGINT + f[j][j + i - 1] + f[j + 1][j + i] + ((s.charAt(j) == s.charAt(j + i))? 1 : -f[j + 1][j + i - 1])) % BIGINT;
		System.out.println(f[0][n - 1]);
	}

}
